package com.xiaobai.frame.config;

import lombok.Getter;
import org.springframework.stereotype.Component;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


/**
 * 前缀树  (暂时用于敏感词替换)
 */
@Component
public class TrieTree {

    /**
     * 前缀树总的词语数
     */
    private int size;

    /**
     * 根节点
     */
    private Node root = new Node(new HashMap<>(), false);


    /**
     * 创建一个新的树节点的类
     */
    private static class Node {
        @Getter
        //Character类是封装一个基本数据类型char的
        private Map<Character, Node> childNodeMap;
        private boolean isWord;

        private Node(Map<Character, Node> childNodeMap, boolean isWord) {
            this.childNodeMap = childNodeMap;
            this.isWord = isWord;
        }

        public void setIsWord(boolean isWord) {
            this.isWord = isWord;
        }

        public boolean getIsWord() {
            return isWord;
        }

        public void setChildNodeMap(Map<Character, Node> childNodeMap) {
            this.childNodeMap = childNodeMap;
        }
    }



    /**
     * 清空前缀树
     */
    public void clear() {
        root = new Node(new HashMap<>(), false);
        size = 0;
    }

    /**
     * 获取前缀树的词语数
     */
    public int size() {
        return size;
    }

    /**
     * 向前缀树中增加节点
     */
    public void add(String[] addValues) {
        if (addValues != null) {
            Arrays.stream(addValues).forEach(this::add);
        }
    }

    /**
     * 向前缀树中增加节点
     */
    public void add(List<String> addValues) {
        if (addValues != null) {
            addValues.forEach(this::add);
        }
    }

    /**
     * 向前缀树中增加节点
     */
    public void add(String str) {
        if (str == null || str.trim().isEmpty()) {
            return;
        }
        //拿到初始化的根节点
        Map<Character, Node> fatherNodeMap = root.childNodeMap;
        int index = 0;
        int addValueLength = str.length();
        //如果index长度不等于传入添加节点字符串的长度就循环下去
        while (index != addValueLength) {
            char ch = str.charAt(index);
            //当前节点下面的子节点包含当前的字符
            if (fatherNodeMap.containsKey(ch)) {
                //获取到该字符下面的Node节点
                Node node = fatherNodeMap.get(ch);
                //判断该下标是不是字符串的最后一个字符串
                if (index != addValueLength - 1) {
                    if (node.childNodeMap == null) {
                        node.childNodeMap = new HashMap<>();
                    }
                    fatherNodeMap = node.childNodeMap;
                } else {
                    //给当前节点设置为一个敏感词的最后一个字
                    if (!node.isWord) {
                        node.setIsWord(true);
                        size++;
                    }
                }
            } else {  //当前节点下面的子节点不包含当前的字符
                if (index != addValueLength - 1) {
                    Node nodeNew = new Node(new HashMap<>(), false);
                    fatherNodeMap.put(ch, nodeNew);
                    fatherNodeMap = nodeNew.childNodeMap;
                } else {
                    //如果是最后一个字符就设置子节点为null
                    Node nodeNew = new Node(null, true);
                    fatherNodeMap.put(ch, nodeNew);
                    size++;
                }
            }
            index++;
        }
    }

    /**
     * 返回前缀树上以 inputStr 开头的词语
     */
    public List<String> matchStartWord(String inputStr) {
        List<String> matches = new ArrayList<>();
        if (root.childNodeMap.isEmpty()) {
            return matches;
        }
        Node node = havaWord(inputStr, root, matches);
        if (node != null) {
            getMatchStr(new StringBuilder(inputStr), new StringBuilder(), matches, node.childNodeMap);
        }
        return matches;
    }

    private void getMatchStr(StringBuilder inputStr,
                             StringBuilder afterStr,
                             List<String> matches,
                             Map<Character, Node> childNodeMap) {
        if (childNodeMap != null) {
            //循环该节点下面的子节点
            for (Map.Entry<Character, Node> m : childNodeMap.entrySet()) {
                //获取到该节点的字符
                Character key = m.getKey();
                StringBuilder afterStr1 = new StringBuilder(afterStr);
                afterStr1.append(key);

                Node node = m.getValue();
                boolean isWord = node.getIsWord();
                //拿到传入字符串的所有字符
                StringBuilder inputStrOrigin = new StringBuilder(inputStr);
                //表示是一个词的结尾
                if (isWord) {
                    matches.add(inputStrOrigin.append(afterStr1).toString());
                }
                if (node.childNodeMap != null) {
                    if (!isWord) {
                        //递归出节点下面的子节点
                        getMatchStr(inputStrOrigin.append(afterStr1), new StringBuilder(), matches, node.childNodeMap);
                    } else {
                        getMatchStr(inputStrOrigin, new StringBuilder(), matches, node.childNodeMap);
                    }
                }
            }
        }
    }


    /**
     * 从前缀树中删除词语 str
     * 如果 str 每个字符节点下都只有其下一个字符节点，并且最后一个字符节点下没有节点则可以从根节点删除这个词语，否则将词语的最后一个字符的词语标识设置为false
     */
    public void deleteWord(String str) {
        //判断前缀树上是否有该词语
        if (null != str && haveWord(str)) {
            int index = 0;
            Node deleteNode = null;
            Node startNode = root;
            char[] charArray = str.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
                char ch = charArray[i];
                Map<Character, Node> childNodeMap = startNode.childNodeMap;
                //判断如果当前节点字符是不是最后一个字符
                Node node = childNodeMap.get(ch);
                if (i != charArray.length - 1) {
                    //如果该节点下面还有子节点或者该节点是一个敏感词的结尾 就修改
                    if (node.childNodeMap.size() > 1 || node.isWord) {
                        deleteNode = node;
                        index = i;
                    }
                    startNode = node;
                } else {
                    Map<Character, Node> childNodeMap1 = node.childNodeMap;
                    //修改标识,删除该敏感词
                    node.isWord = false;
                    if (null != childNodeMap1 && !childNodeMap1.isEmpty()) {
                        //如果该最后一个字符不是叶子节点，即它还有子节点
                        deleteNode = null;
                    } else {
                        //如果该最后一个字符是叶子节点
                        if (deleteNode == null) {
                            deleteNode = root;
                        } else {
                            index++;
                        }
                    }
                }
            }

            if (deleteNode != null) {
                Map<Character, Node> childNodeMap = deleteNode.childNodeMap;
                if (childNodeMap.size() > 1) {
                    childNodeMap.remove(str.charAt(index));
                } else {
                    deleteNode.childNodeMap = null;

                }
            }
            size--;
        }
    }


    /**
     * 判断前缀树上的所有词语，词语  str
     */
    public boolean haveWord(String str) {
        if (null == str) {
            return false;
        }
        List<String> list = new ArrayList<>();
        havaWord(str, root, list);
        return !list.isEmpty() && str.equals(list.get(0));
    }

    /**
     * 判断前缀树上的所有词语，是否有 str 开头的
     */
    public boolean startWordWith(String str) {
        if (null == str) {
            return false;
        }
        List<String> list = new ArrayList<>();
        Node node = havaWord(str, root, list);
        if (list.isEmpty()) {
            return node != null;
        }
        return list.size() == 1 && str.equals(list.get(0));
    }

    /**
     * 判断前缀树上是否有 以 inputStr 开头的词语，
     * -有,则返回 inputStr 最后一个字符的子节点,若最后一个节点没有子节点则返回最后一个字符的节点
     *      若返回的节点不为 null，且 matches 的大小为 0，则返回的是最后一个字符的子节点
     *          （即表明 inputStr 是前缀树上的一个词语的开头，如：前缀树上有 “一生一世” 这个词，但 inputStr 是 “一生一”）
     *      若返回的节点不为 null，且 matches 的大小为 1，则返回的是 inputStr 倒数第二个字符的节点
     *          （即表明 inputStr 是前缀树上的一个词语，如：前缀树上有 “一生一世” 这个词，但 inputStr 是 “一生一世”）
     * -没有,则返回 null
     */
    private Node havaWord(String inputStr, Node startNode, List<String> matches) {
        char[] charArray = inputStr.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char ch = charArray[i];
            Map<Character, Node> childNodeMap = startNode.childNodeMap;
            //如果该字符不是在这个节点的子节点里面的话就直接返回null
            if (!childNodeMap.containsKey(ch)) {
                return null;
            }
            Node node = childNodeMap.get(ch);
            //如果拿到这节点下面的子节点没有,然后这个字符又不是最后一个字符的话就直接返回null,说明就没有这个词语
            if (node.childNodeMap == null && i != charArray.length - 1) {
                return null;
            }
            //如果这个节点下面的子节点为null,而且传入的字符串只有一个字符,就把节点订到目前字符的节点上面来
            if (node.childNodeMap != null || charArray.length == 1) {
                startNode = node;
            }
            //传入的数组不为null,而且当前下标是字符串的最后一个字符,在前缀树里面也给该节点标为了是一个敏感词的结尾
            if (null != matches && i == charArray.length - 1 && node.isWord) {
                matches.add(inputStr);
            }
            //说明该前缀树上有该敏感词,但是这个敏感词下面没有其他词语了
            if (i == charArray.length - 1 && node.isWord && node.childNodeMap == null) {
                return null;
            }
        }
        return startNode;
    }


    /**
     * 字符串敏感词替换，若 text 文本中的的词语有在前缀树上的，将其替换为 *
     */
    public String sensitiveWordReplace(String text) {
        return text != null ? markWordAndWordReplace(text, null, null) : null;
    }

    /**
     * 字符串敏感词标记，若 text 文本中的的词语有在前缀树上的，用 startSymbol和 endSymbol 将其标记
     * 如：
     * 例1：
     * 假如 "张三"、"今天" 这两个词语在前缀树上
     * 当调用 markWord("张三你好，你今天过得怎么样", "【", "】")；
     * 得到的结果是 "【张三】你好，你【今天】过得怎么样"
     */
    public String markWord(String text, String startSymbol, String endSymbol) {
        if (text != null && startSymbol != null && endSymbol != null) {
            return markWordAndWordReplace(text, startSymbol, endSymbol);
        }
        return text;
    }

    //敏感词替换、敏感词标记通用方法
    private String markWordAndWordReplace(String text, String startSymbol, String endSymbol) {
        Node startNode = root;
        //isMarkWord 为 true 则为敏感词标记，false 为敏感词替换
        boolean isMarkWord = startSymbol != null && endSymbol != null;
        //存储最终的结果
        StringBuilder result = new StringBuilder();
        //若为敏感词替换（也就是isMarkWord为false）starOrCh用于存放* ，即匹配到一个字符就存入* 。若为敏感词标记，则starOrCh用于存放匹配的词
        StringBuilder starOrCh = new StringBuilder();
        //存放匹配到的字符，即匹配到一个字符就存入
        StringBuilder matchCh = new StringBuilder();
        int index = 0;
        while (index != text.length()) {
            char ch = text.charAt(index);
            Map<Character, Node> childNodeMap = startNode.childNodeMap;
            if (childNodeMap.containsKey(ch)) {
                starOrCh.append(isMarkWord ? ch : "*");
                Node node = childNodeMap.get(ch);
                if (node.childNodeMap != null) {
                    startNode = node;
                }
                if (node.isWord) {
                    StringBuilder saveTemp = new StringBuilder(starOrCh);
                    //判断该字符后的字符在前缀树上是否在该词语的后面（如：text是"张力懦夫"，当前字符ch是"张"，
                    // 匹配到"张力"这个词语，但是"张力懦夫"也是个词语，需要向后再判断其是否在前缀树上，并判断其是否是一个词语）
                    int nextWordEndIndex = nextCh(text, index + 1, index, node);
                    //说明在现在这个节点后面还有其他节点可以和节点也可以匹配(这个敏感词开头的后面还有其他长的敏感词也和文本匹配)
                    if (nextWordEndIndex > index) {
                        int nextStart = index + 1;
                        StringBuilder temp = new StringBuilder();
                        temp.append(saveTemp);
                        //循环到最长长度的哪个词
                        for (int i = nextStart; i <= nextWordEndIndex; i++) {
                            char nextCh = text.charAt(i);
                            temp.append(isMarkWord ? nextCh : "*");
                            index++;
                        }
                        appendResultClearTemp(result, temp, matchCh, starOrCh, startSymbol, endSymbol);
                    } else {
                        //将该词语用*号替换拼接到result , 并清空 starOrCh、temMatch
                        appendResultClearTemp(result, starOrCh, matchCh, starOrCh, startSymbol, endSymbol);
                    }
                    //重新设置根节点为开始遍历的节点，方便下一个字符匹配
                    startNode = root;
                } else {
                    matchCh.append(ch);
                }
            } else {//就是下一个字符没在该节点的子节点下面
                //存放匹配到的字符,的里面有数据  也就是不是root节点  (词语的前几个字和敏感词当中的某个词宇前几个字相同)
                if (!matchCh.isEmpty()) {
                    //把获取到的匹配的字放到最终的数据当中,并清除matchCh和starOrCh的数据
                    appendResultClearTemp(result, matchCh, matchCh, starOrCh);
                }
                startNode = root;
                //如果上面没有匹配到对应的,重新把字符重置到根节点root节点重新判断
                if (startNode.childNodeMap.containsKey(ch)) {
                    matchCh.append(ch);
                    starOrCh.append(isMarkWord ? ch : "*");
                    startNode = startNode.childNodeMap.get(ch);
                } else {
                    //如果在根节点没有匹配到的话就把最新节点返回到根节点上面
                    result.append(ch);
                }
            }
            index++;
        }
        return result.toString();
    }

    /**
     *
     * @param result 存储最终的结果
     * @param joinBuilder 若为敏感词替换（也就是isMarkWord为false）starOrCh用于存放* ，即匹配到一个字符就存入* 。若为敏感词标记，则starOrCh用于存放匹配的词
     * @param matchCh 存放匹配到的字符，即匹配到一个字符就存入
     * @param starOrCh 若为敏感词替换（也就是isMarkWord为false）starOrCh用于存放* ，即匹配到一个字符就存入* 。若为敏感词标记，则starOrCh用于存放匹配的词
     * @param startSymbol
     * @param endSymbol
     */
    private void appendResultClearTemp(StringBuilder result,
                                       StringBuilder joinBuilder,
                                       StringBuilder matchCh,
                                       StringBuilder starOrCh,
                                       String startSymbol,
                                       String endSymbol) {
        //如果是敏感词标记的话就会在前后都要标记一下
        if (startSymbol != null) {
            result.append(startSymbol);
        }
        result.append(joinBuilder);
        if (endSymbol != null) {
            result.append(endSymbol);
        }
        //重新设置长度(清空数据)
        matchCh.setLength(0);
        starOrCh.setLength(0);
    }

    private void appendResultClearTemp(StringBuilder result, StringBuilder joinBuilder, StringBuilder matchCh, StringBuilder starOrCh) {
        result.append(joinBuilder);
        matchCh.setLength(0);
        starOrCh.setLength(0);
    }

    //返回从text 的 index 下标开始，node 节点下匹配到的最长词语，返回最长的词语的最后一个字符在 text 的下标，即 wordIndex
    private int nextCh(String text, int index, int wordIndex, Node node) {
        if (index <= text.length() - 1) {
            char nextCh = text.charAt(index);
            Map<Character, Node> childNodeMap = node.childNodeMap;
            if (childNodeMap != null) {
                if (childNodeMap.containsKey(nextCh)) {
                    Node nextNode = childNodeMap.get(nextCh);
                    if (nextNode.isWord) {
                        wordIndex = index;
                    }
                    return nextCh(text, index + 1, wordIndex, childNodeMap.get(nextCh));
                } else {
                    return wordIndex;
                }
            }
        }
        return wordIndex;
    }
}


